#include<vector>
#include<string>
#include<iostream>

class QueenRecord {
private:
    std::vector<bool> column;
    std::vector<bool> row;
    std::vector<bool> plus;
    std::vector<bool> sub;
    int n;
public:
    QueenRecord(int n): n(n) {
        column.resize(n, false);
        row.resize(n, false);
        plus.resize(2*n-1, false);
        sub.resize(2*n-1, false);
    }
    inline void addQueen(int rowid, int colid) {
        column[colid] = true;
        row[rowid] = true;
        plus[rowid+colid] = true;
        sub[rowid-colid+n-1] = true;
    }
    inline bool isSafe(int rowid, int colid) {
        return !(column[colid] || row[rowid] || plus[rowid+colid] || sub[rowid-colid+n-1]);
    }
    inline void removeQueen(int rowid, int colid) {
        column[colid] = false;
        row[rowid] = false;
        plus[rowid+colid] = false;
        sub[rowid-colid+n-1] = false;
    }
};

void solveNQueens(int rowid, int n, std::vector<int>& board, std::vector<std::vector<int>>& solutions, QueenRecord& record) {
    if (rowid == n) {
        solutions.push_back(board);
        return;
    }
    for (int colid = 0; colid < n ; colid++) {
        if (record.isSafe(rowid, colid)) {
            board[rowid] = colid;
            record.addQueen(rowid, colid);
            solveNQueens(rowid+1, n, board, solutions, record);
            record.removeQueen(rowid, colid);
        }
    }
}

std::vector<std::vector<int>> solveNQueens1(int n){
    std::vector<std::vector<int>> solutions;
    std::vector<int> board(n,0);
    QueenRecord record(n);
    solveNQueens(0, n, board, solutions, record);
    return solutions;
}

class Solution {
public:
    std::vector<std::vector<std::string>> solveNQueens(int n){
        std::vector<std::vector<int>> num_results = solveNQueens1(n);
        std::vector<std::vector<std::string>> res;
        for (auto& num_result : num_results) {
            std::vector<std::string> result;
            for (int i = 0; i < n; i++) {
                std::string row;
                for (int j = 0; j < n; j++) {
                    if (num_result[i] == j) {
                        row += "Q";
                    } else {
                        row += ".";
                    }
                }
                result.push_back(row);
            }
            res.push_back(result);
        }
        return res;
    }

};

int main() {
    int N = 4;

    Solution sol;
    auto results = sol.solveNQueens(N);
    for (auto& result : results) {
        for (auto& row : result) {
            std::cout << row << std::endl;
        }
        std::cout << std::endl;
    }

    return 0;
}